Search in Rotated Sorted List

Medium

Question

You're given a list that was originally sorted but may have been rotated at some point.

For example, the original list could be: [1, 2, 3, 4, 5, 6], and then rotated to become: [4, 5, 6, 1, 2, 3].

Return the index of a given target in the list, or return -1 if the target does not exist in the list.

Note: Solve this problem in O(logn) time.

Input: nums = [9, 11, 0, 2, 3, 6], target = 0

Output: 2

The target 0 is at index 2 in the list.

Input: nums = [5, 6, -5, -2, -1, 0, 1], target = 8

Output: -1

The target 8 is not in this list.

Input: nums = [3, 7], target = 3

Output: 0

The target 3 is at index 0 in this list.

What are some questions you'd ask an interviewer?

In the context of this problem, what value would you return if given these inputs? num = [6, 7, 8, 9, 10, 1, 2, 3, 4, 5], target = 2

-1